import java.util.Arrays;

/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: 掌握堆排序
 * @date 2025/7/15 14:42
 */

public class HeapSortIterative {

    /**
     * 堆排序入口方法
     * @param arr 待排序数组
     */
    public static void heapSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }

        int n = arr.length;

        // 1. 构建最大堆（从最后一个非叶子节点开始）
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(arr, n, i); // 使用迭代版 heapify
        }

        // 2. 排序：逐个将堆顶元素（最大值）交换到数组末尾，并调整堆
        for (int i = n - 1; i > 0; i--) {
            // 交换堆顶和当前未排序部分的最后一个元素
            swap(arr, 0, i);
            // 对剩余元素重新调整成最大堆
            heapify(arr, i, 0); // 使用迭代版 heapify
        }
    }

    /**
     * 迭代版 heapify（调整最大堆）
     * @param arr 数组
     * @param heapSize 当前堆的大小
     * @param i 当前需要调整的节点索引
     */
    private static void heapify(int[] arr, int heapSize, int i) {
        int current = i;
        while (true) {
            int largest = current;  // 初始化当前节点为最大值
            int left = 2 * current + 1;  // 左子节点索引
            int right = 2 * current + 2; // 右子节点索引

            // 如果左子节点存在且大于当前最大值
            if (left < heapSize && arr[left] > arr[largest]) {
                largest = left;
            }

            // 如果右子节点存在且大于当前最大值
            if (right < heapSize && arr[right] > arr[largest]) {
                largest = right;
            }

            // 如果最大值不是当前节点，则交换并继续调整
            if (largest != current) {
                swap(arr, current, largest);
                current = largest; // 移动到子节点继续调整
            } else {
                break; // 当前节点已满足最大堆条件，退出循环
            }
        }
    }

    /**
     * 交换数组中两个元素的位置
     */
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("排序前：" + Arrays.toString(arr));
        heapSort(arr);
        System.out.println("排序后：" + Arrays.toString(arr));
    }
}
